COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	examples, exercises, exam problems, and projects
C00006 00003	.if false then begin "problems"
C00010 00004	.if false then begin "solutions"
C00012 ENDMK
C⊗;
examples, exercises, exam problems, and projects

1. Basic LISP.
alt, fancy alt, (indebted to Allen Newell for this example)
subst, equal, member, sublis, path, adjoin, append,
union, intersection, difference, Cartesian product,
differentiation (2 term and multi-term sums and products),
maplist,andlis, orlis,  exactness of differential equation,
canonical forms of ( polynomials, boolean expressions, 
rational functions, conditional expressions)
elementary simplifications syntax directed,
elementary compilation syntax directed,
elementary I-O syntax directed,
various sorts, multiplication of permutations and elements
of the group algebra,

2. Projects.
	a. For mathematicians:  Equivalence of
two dimensional manifolds, computation of homology
groups of simplicial manifolds, factorization of
algebraic integers, factorization of polynomials with large
integers as coefficients and also factorization over
algebraic number fields, computation of representations
of groups, computation of Galois groups, compute representation
of symmetric functions in terms of elementary symmetric
functions, generalize this to polynomials invariant under
a group of permutations,

	b. For hackers and computer  scientists:  Hash  facility  for
LISP,  specs  of  LISP  1.7,  a  good syntax directed system, a truly
optimal compiler, solve the functional argument problem,
improve Quam I-O, better interactive facilities,
better numerical computation, better library, LISP 2,
a LISP system suitable for all purposes, e.g. with good
imbedded ALGOL and machine language and facilities for
handling packed data and a variety of storage control
mechanisms.
invariant hash,

	c. Applications: Better MATHLAB, resolution
package,  integration proof checker,
MATHLAB at Stanford, trigonometric identity proof checker,
contour integration proof checker,
improvements to REDUCE (e.g. better matrix package, better
matrix inversion, better error messages, (call Hearn),
improved simplification heuristics), display of mathematical
exprssions and their entry using the display (Hearn)
Collins gcd for polynomials, Berlekamp algorithms,


3. Theory
recursion induction problems
alt pair[x,y] = x
x*[y*z] = [x*y]*z
reverse reverse x = x
reverse x*y = [reverse y] * [reverse x]
andlis[x*y,p] = andlis[x,p] ∧ andlis[y,p]

correctness of elementary compiler

where does and where must lisp spend its time
.if false then begin "problems"

1.  Write down  an S-expression  A with the  property that  eval(A,NIL)=A.
(Hint: use the function SUBST)

    2.  A real number  generator is a function  f which maps the  integers
into the set of decimal digits 0,1...9, the idea being that f(n)= the  nth
digit after the decimal  point of the real  number "generated" by f.   The
values of  the  function on  non-positive  integers determine  the  digits
before the decimal point in the obvious way.  We restrict our attention to
functions f with the property that only  a finite number of its values  on
non-positive integers are non-zero (no "infinite" numbers allowed!).   For
example the real number generator(λx.if x≤-2 then 0 else 3) generates  the
real number  33.3333....   =  33  1/3.   (Only  positive  numbers  can  be
represented using this  scheme; extension  of the scheme  to the  negative
numbers would be trivial)  You are to write  an addition routine for  real
number generators.  This will  be a functional  PLUS which,given two  real
number generators f and g, returns a real number generator PLUS(f,g) which
generates the sum of the real numbers generated by f and g.  In fact  this
task as stated  is impossible,since  no functional  PLUS which  represents
addition of real numbers can have the property that its output is always a
total function when its inputs are total.  (Why?)  Thus we must relax  our
conditions:  whenever PLUS(f,g) terminates on input n, the value  returned
must be the  nth digit of  the sum of  the numbers generated  by f and  g.
(Note  that  the  function  which  is  undefined  everywhere  meets  these
conditions; however you can  certainly do better than  that.  At the  very
least PLUS should return a total  function when its arguments have only  a
finite number  of non-zero  digits.)   If you  enjoyed writing  plus,  try
writing more pieces of an arithmetic package for real number generators.

    3.  (Hard)  Write  a lisp  expression  f such  that  apply(f,x)=x!  (x
factorial), observing the following restriction:  f must be an  expression
in pure LISP (no PROGs) which does not use the LABEL construct.

.end "problems"
.if false then begin "solutions"

(DEFPROP OY
 (LAMBDA (F)
  (LIST (LIST (QUOTE LAMBDA) (QUOTE (X)) (LIST F (QUOTE (LIST (QUOTE QUOTE) (X (LIST (QUOTE QUOTE) X))))))
        (LIST (QUOTE QUOTE)
              (LIST (QUOTE LAMBDA)
                    (QUOTE (X))
                    (LIST F (QUOTE (LIST (QUOTE QUOTE) (X (LIST (QUOTE QUOTE) X)))))))))
EXPR)

(DEFPROP Y
 (LAMBDA (F)
  (LIST (LIST (QUOTE LAMBDA) (QUOTE (X)) (LIST F (QUOTE (LIST X (LIST (QUOTE QUOTE) X)))))
        (LIST (QUOTE QUOTE)
              (LIST (QUOTE LAMBDA) (QUOTE (X)) (LIST F (QUOTE (LIST X (LIST (QUOTE QUOTE) X))))))))
EXPR)

(DEFPROP FAC
 (LAMBDA (F)
  (LIST (QUOTE LAMBDA)
        (QUOTE (X))
        (LIST (QUOTE COND)
              (QUOTE ((EQ X 0) 1))
              (LIST T (LIST (QUOTE TIMES) (LIST F (QUOTE (SUB1 X))) (QUOTE X))))))
EXPR)

.end "solutions"